The computing industry, like so many other technologies, has seen and continues to experience quantum improvements in design, efficiency, memory management, speed and many other features that are characterized as enhancing the computer's operation. Many of the improvements have centered around the Central Processing Unit (CPU) and its interaction with the Operating System (OS) executed by the CPU.
One area of improvement concerning the operation of the CPU has led to vast improvements in memory management and the concept of the virtual memory system. The virtual memory system was adopted in large part due to the limitations that fixed, physical memory space presented to OS developers. Virtually all software applications executing within the parameters of the CPU utilize physical memory space for temporary storage of machine language program instructions and operands used by the machine language program. The earlier OS designs strictly limited memory usage to the physical memory available to the CPU. The physical memory available to the CPU being realized by either Random Access Memory (RAM) or magnetic disk storage units, the access to which severely limited or even prohibited the existence of a multi-tasking OS, not to mention a system comprising multiple CPUs operating in parallel.
A number of techniques have been created over the years to handle limited physical memory situations. One such technique was the overlay system, in which a program was divided into discrete segments where only one of the segments could be accessed at one time. Whenever a different segment of program was needed, it was simply loaded into the physical memory space available to the CPU, and loaded over the top of the old program segment previously executed.
A second technique that has become prevalent today is the use of virtual memory space. Virtual memory expands on the overlay concept and divides all available memory into a set of pages. In general, the pages are restricted to one, or perhaps a few, possible page sizes. Instead of having only a single overlay region, multiple overlay regions may be created, where one overlay region is created for each page of memory available. The initial offering of overlays required that the application programmer be diligent in his determination of the layout of the data. Over time, however, standard software packages became available to manage the overlay map and eventually, the overlay management functionality migrated into the OS.
Virtual memory also establishes the concept of address spaces. Prior to virtual memory, a single address space was defined by the number of address bits available to access the memory space. A 16-bit address bus, for example, allowed access to an address space of only 64 kilobytes (KB). Some architectures allowed the separation of instruction code from instruction data so that the combined address space could be doubled to 128 KB. These architectures, however, still limited the software applications to the absolute maximum of 64 KB, not including the address space required for the OS itself.
A level of indirection was added by the use of virtual memory to the application space concept, which allowed the OS to maintain a multitude of different address spaces, only one of which being active at any given time. Separate address spaces for each application yielded the protection of the memory owned by the application because each application was confined to its own virtual memory space. Additionally, the advent of relatively inexpensive magnetic storage media increased the amount of memory available to the CPU and allowed the CPU to swap data between RAM and magnetic storage in order to simulate a much larger physical memory space and thus a much larger virtual memory space.
A CPU running in virtual memory mode receives addresses which are regarded as virtual addresses and are required to be converted into a physical address pointing to a physical memory location. For example, a CPU may receive an instruction pointer, which points to an address location of the next instruction to execute of a particular user program. The address location, however, is not the physical address location containing the instruction being executed, but is rather a virtual address. Before fetching the instructions to be executed, the CPU must translate the virtual address to a physical address and then fetch the contents of the physical memory from the physical address. The address translations may be stored in a cache memory, which allows the CPU to track the latest address conversions performed. If, for example, a virtual address translation has already been performed for the next instruction fetch, then the translation process need not be repeated. Instead, an address translation lookup into the translation cache is all that is required to obtain the address for the next operation to be performed.
If the translation cache does not contain the necessary information, then the memory management portion of the CPU must perform the required address translation. Memory management systems may use a paging system to calculate the physical address from the virtual address. That is to say, that the CPU utilizes page table support to determine which one of many page tables may contain the cached address translation. The directory page table may consist of a set of entries, each pointing to a page table. Each page table entry in turn consists of a number of entries, which points to a page of physical memory. The CPU, therefore, looks at the virtual address as a three-part address: 1.) A directory offset; 2.) A page table offset; and 3.) A page offset to determine the physical address from the virtual address.
Prior art address translation schemes use a hardware based page table implementation to perform comparisons on virtual memory ranges to speed up the identification of which page table contains the translation of the virtual address of interest. That is to say, that each page table contained a lower virtual memory limit and an upper virtual memory limit. A pair of comparators, therefore, could be used to simultaneously compare the lower and upper limits of two page tables to quickly isolate which, if any, page table contained the address translation of the virtual address of interest. If neither of the two page tables contained the address translation, then a miss would be recorded for the particular page table pair and a new page table pair would then be simultaneously compared, and so on. The hardware implementation, however, requires dedicated registers and comparators, which are not available in a software emulation environment. When the hardware architecture of the CPU is required to be emulated, which is often the case during user program testing and troubleshooting, a software alternative to the hardware address translation is required. Translation path lengths become troublesome for the software alternative due to the sequential operation of the software emulated address translation function.
A need exists, therefore, for a software emulated address translation technique that substantially reduces the translation path lengths required by the technique and thus accelerates the overall operation of the software emulated platform.